home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 #2 / Ham Radio 2000 - Volume 2.iso / HAMV2 / ANTENNA / YAGIU112 / GA_LIB.C < prev    next >
C/C++ Source or Header  |  1995-08-15  |  7KB  |  337 lines
  1. #include <string.h>
  2. #ifndef GCC
  3. #include <stdlib.h>
  4. #endif
  5. #include <values.h>
  6. #include <math.h>
  7. #include <sys/types.h>
  8. #ifdef i386
  9. #ifdef UNIX
  10. #include <time.h>
  11. #endif
  12. #elif
  13. #include <sys/time.h>
  14. #endif
  15.  
  16. #ifdef i386 
  17. #ifndef DOS
  18. #include <ieeefp.h> /* Needed for isnan() on PC running unix */
  19. #endif
  20. #endif
  21. #include <errno.h>
  22. #include "yagi.h"
  23.  
  24.  
  25.  
  26. typedef struct {
  27.     int parent1,parent2 ;
  28.     char *gene ;
  29.     double fitness ;
  30.     } GeneRecord ;
  31.  
  32.  
  33. int population_size=0 ;
  34. int gene_length=0 ;
  35. int elite=1 ;
  36. int ramp=0 ;
  37. int PRINT=1 ;
  38. double MX ; 
  39. /* double pmutate=0.4 ;
  40. double pcross=0.6 ;
  41. double psimplex=0.4 ;
  42. double ptrans=0.2 ; */
  43. double pmutate=0.1 ; 
  44. double pcross=0.9 ;
  45. double psimplex=0.5 ;
  46. double ptrans=0.03 ;
  47. extern int errno;
  48.  
  49. GeneRecord *Pop1=NULL,*Pop2=NULL ;
  50.  
  51. void setprobs(double pm,double pc,double ps,double pt)
  52. {
  53.     pmutate=pm ;
  54.     pcross=pc ;
  55.     psimplex=ps;
  56.     ptrans=pt ;
  57. }
  58.  
  59. int GA_Free(void) 
  60. {
  61.     int a ;
  62.     if (Pop1!=NULL) {
  63.         for(a=0 ; a<population_size ;a++)
  64.             if (Pop1[a].gene!=NULL) free(Pop1[a].gene) ;
  65.         free((char *) Pop1) ;
  66.     }
  67.     if (Pop2!=NULL) {
  68.         for(a=0 ; a<population_size ;a++)
  69.             if (Pop2[a].gene!=NULL) free(Pop2[a].gene) ;
  70.         free((char *) Pop2) ;
  71.     }
  72. }
  73.  
  74. int GA_Error(char *ErrorMsg) 
  75. {
  76.     int a ;
  77.     if (Pop1!=NULL) {
  78.         for(a=0 ; a<population_size ;a++)
  79.             if (Pop1[a].gene!=NULL) free(Pop1[a].gene) ;
  80.         free(Pop1) ;
  81.     }
  82.     if (Pop2!=NULL) {
  83.         for(a=0 ; a<population_size ;a++)
  84.             if (Pop2[a].gene!=NULL) free(Pop2[a].gene) ;
  85.         free(Pop2) ;
  86.     }
  87.     fprintf(stderr,"GA_LIB Error : %s \n\n",ErrorMsg) ;
  88.     exit(1) ;
  89. }       
  90.  
  91. double GetMax()
  92. {
  93.     return(MX) ;
  94. }
  95.  
  96. void SetPrint(int a)
  97. {
  98.     PRINT=a; 
  99. }
  100. void dump_pop1(FILE *fd,int generation,double max,double aver) 
  101. {
  102.     int a ;
  103.  
  104.     if (PRINT==0) return ;
  105.     fprintf(fd,"Current contents of population: generation %d\n",generation);
  106.     for(a=0 ; a<gene_length ; a++) fprintf(fd,"-");
  107.     fprintf(fd,"------------------\n");
  108.     fprintf(fd,"Par1 Par2 Fitness   Code\n");
  109.     for(a=0 ; a<population_size ; a++)
  110.         fprintf(fd,"%4d %4d %9.4f %s\n",Pop1[a].parent1,Pop1[a].parent2,Pop1[a].fitness,Pop1[a].gene);
  111.     fprintf(fd,"\n Maximum %9.4lf Average %9.4lf\n",max,aver);
  112.     for(a=0 ; a<gene_length ; a++) fprintf(fd,"-");
  113.     fprintf(fd,"------------------\n\n");
  114. }        
  115.  
  116. int Initialise(int PopSize, int GeneSize) 
  117. {
  118.     int a,b ;
  119.     char c[2] ;
  120.     
  121.     c[1]=0 ;
  122.  
  123.     /* srandom(time(&a)); */
  124.     ramp=0 ;
  125.     population_size=PopSize ;
  126.     gene_length=GeneSize+1 ;
  127.     /* limit population size */
  128.     if ((PopSize<20)||(PopSize>1000)) GA_Error("Bad parameters to Initialise") ;
  129.     /* Allocate memory for population 1 */
  130.     Pop1=(GeneRecord *)calloc(PopSize,sizeof(GeneRecord)) ;
  131.     /* Mem alloc error */
  132.     if (Pop1==NULL) GA_Error((char *)"Memory allocation for population 1") ;
  133.     /* Blank population array */
  134.     for (a=0 ; a<population_size ; a++) {
  135.         Pop1[a].gene=NULL ;
  136.         Pop1[a].parent1=0 ;
  137.         Pop1[a].parent2=0 ;
  138.         Pop1[a].fitness=0.0 ;
  139.     }
  140.     /* Allocate memory for genes */
  141.     for (a=0 ; a<population_size ; a++) 
  142.         if ((Pop1[a].gene=malloc(gene_length))==NULL) 
  143.             GA_Error("Cannot allocate gene in population 1");
  144.     /* Allocate memory for population 2 */
  145.     Pop2=(GeneRecord *)calloc(PopSize,sizeof(GeneRecord)) ;
  146.     /* Mem alloc error */
  147.     if (Pop2==NULL) GA_Error((char *)"Memory allocation for population 1") ;
  148.     /* Blank population array */
  149.     for (a=0 ; a<population_size ; a++) {
  150.         Pop2[a].gene=NULL ;
  151.         Pop2[a].parent1=0 ;
  152.         Pop2[a].parent2=0 ;
  153.         Pop2[a].fitness=0.0 ;
  154.     }
  155.     /* Allocate memory for genes */
  156.     for (a=0 ; a<population_size ; a++) 
  157.         if ((Pop2[a].gene=malloc(gene_length))==NULL) 
  158.             GA_Error("Cannot allocate gene in population 2");
  159.     /* Initialise genes */
  160.     for (a=0 ; a<population_size ; a++) {
  161.         for (b=0 ; b<GeneSize ; b++) 
  162.             /* Pop1[a].gene[b]=(char)(48+(randint()&1)) ;XXXXXXXX */
  163.             Pop1[a].gene[b]=(char)(48+(randint()&1)) ;
  164.         Pop1[a].gene[GeneSize]=0 ;
  165.     }
  166.  
  167. #ifdef DEBUG
  168.     if(errno)
  169.     {
  170.         fprintf(stderr,"Errno =%d in Initialise() of ga_lib.c\n", errno);
  171.         exit(1);
  172.     }
  173. #endif
  174.     return (0) ;
  175. }
  176.  
  177. void crossover(char *s1,char *s2)
  178. {
  179.     int point;
  180.     char duplic ;
  181.     
  182.     /* only works for strings of same length */
  183.     if (strlen(s1)!=strlen(s2)) GA_Error((char *)"Gene length mismatch for crossover") ;
  184.     /* choose a point and swap tails of strings */
  185.     for (point=(randint()%(strlen(s1)-2))+1 ; point <strlen(s1) ; point++)
  186.     {
  187.         duplic=s1[point] ;
  188.         s1[point]=s2[point] ;
  189.         s2[point]=duplic ;
  190.     } 
  191. }
  192.  
  193. void mutate(char *s1)
  194. {
  195.     /* flip a bit in at random point */
  196.     s1[randint()%strlen(s1)]^=1 ;
  197. }       
  198.  
  199. int ga_simplex(char *s1,char *s2, char *s3)
  200. {
  201.     int point ;
  202.     for (point=0 ; point <(strlen(s1)-1) ; point++ )
  203.         if (s1[point]==s2[point]) 
  204.             s3[point]=s1[point] ;
  205.         else
  206.             s3[point]=s3[point]^1 ;
  207. }
  208.  
  209. void swap(int *x,int *y)
  210. {
  211.     int t ;
  212.     t=*x ;
  213.     *x=*y ;
  214.     *y=t ;
  215. }       
  216.  
  217. void Sort() 
  218. {
  219.     GeneRecord T ;
  220.     int outer,inner,moved;
  221.     
  222.     for (outer=population_size-1; outer>0 ; outer--)
  223.     {
  224.         moved=0 ;
  225.         for (inner=0 ; inner<outer ; inner++)
  226.         {
  227.             if (Pop1[inner].fitness<Pop1[inner+1].fitness)
  228.             {
  229.                 memcpy((char *) &T,(char *) &Pop1[inner],sizeof(GeneRecord)) ;
  230.                 memcpy((char *) &Pop1[inner],(char *) &Pop1[inner+1],sizeof(GeneRecord)) ;
  231.                 memcpy((char *) &Pop1[inner+1],(char *) &T,sizeof(GeneRecord)) ;
  232.                 moved=1;
  233.             }
  234.         }
  235.         if (moved==0) break ;
  236.     }
  237. }
  238.     
  239. void transloc(char *gene) 
  240. {
  241.     int a,point,gene_size ;
  242.     char *dup;
  243.  
  244.     gene_size=gene_length-1 ;
  245.     point=randint()%gene_size ;
  246.     dup=strdup(gene) ;
  247.     for(a=0 ; a<gene_size ; a++) gene[a]=dup[(a+point)%gene_size] ;
  248.     free(dup);
  249. }
  250.     
  251. int Selection(FILE *fd, int gen)
  252. {
  253.     int a,b,c,select,d ;
  254.     double sigma,rd ;
  255.     GeneRecord *temp ;
  256.     double minfit,maxfit ;
  257.     FILE *tmp;
  258.     sigma=0.0 ;
  259.     minfit=MAXDOUBLE ; 
  260.     maxfit=-minfit ;
  261.     /* minfit=1e308; maxfit=-1e308; XXXXXXXXXXXXXXXXXXXXXX */
  262.     for(a=0 ; a<population_size ; a++ ) 
  263.     {
  264.         Pop1[a].fitness=Objective(Pop1[a].gene) ;
  265.         if (Pop1[a].fitness<minfit) minfit=Pop1[a].fitness ;
  266.         if (Pop1[a].fitness>maxfit) maxfit=Pop1[a].fitness ;
  267.         sigma+=Pop1[a].fitness ;
  268.     }
  269.     MX=maxfit ;
  270.     Sort() ;
  271.     dump_pop1(fd,gen,maxfit,sigma/population_size);
  272.     for(a=0 ; a<population_size ; a++ ) 
  273.     {
  274.         if(minfit!=maxfit)
  275.         {
  276.             Pop1[a].fitness=((Pop1[a].fitness-minfit)*99.0/(maxfit-minfit))+1.0 ;
  277.         }
  278.     }
  279.     ramp++ ;
  280.     sigma=0.0 ;
  281.     for(a=0 ; a<population_size ; a++ ) 
  282.         sigma+=Pop1[a].fitness ;
  283.     c=0 ;
  284.     for(a=0 ; a<population_size ; a++ )
  285.     {
  286.         b=(int) (Pop1[a].fitness*population_size/sigma) ;
  287.         for (d=0 ; d<b ; d++)
  288.             strcpy(Pop2[c++].gene,Pop1[a].gene) ;
  289.     }       
  290.     for(d=c ; d<population_size ; d++)
  291.     {
  292.             b=randint()%population_size ;
  293.             strcpy(Pop2[d].gene,Pop1[b].gene) ;
  294.     }
  295.     for(a=0 ; a<population_size ;a++)
  296.     {
  297.         if (randreal()<pmutate) mutate(Pop2[a].gene) ;
  298.         if (randreal()<ptrans) transloc(Pop2[a].gene) ;
  299.     }
  300.     temp=Pop1 ;
  301.     Pop1=Pop2 ;
  302.     Pop2=temp ;
  303.     for(a=2 ; a<population_size ; a+=2 )
  304.     {
  305.         b=randint()%population_size ;
  306.         c=randint()%population_size ;
  307.         strcpy(Pop2[a].gene,Pop1[b].gene);
  308.         strcpy(Pop2[a+1].gene,Pop1[c].gene);
  309.         if (randreal()<pcross)
  310.         {
  311.             crossover(Pop2[a].gene,Pop2[a+1].gene) ;
  312.             Pop2[a].parent2=Pop2[a+1].parent1 ;
  313.             Pop2[a+1].parent2=Pop2[a].parent1 ;
  314.         } else {
  315.             Pop2[a].parent2=Pop2[a].parent1 ;
  316.             Pop2[a+1].parent2=Pop2[a+1].parent1 ;
  317.         }
  318.     }
  319.     if (randreal()<psimplex) {
  320.         a=randint()%population_size ;   
  321.         b=randint()%population_size ;   
  322.         c=randint()%population_size ;   
  323.         if (Pop1[a].fitness<Pop1[b].fitness) 
  324.             swap(&a,&b) ;
  325.         if (Pop1[b].fitness<Pop1[c].fitness) 
  326.             swap(&b,&c) ;
  327.         if (Pop1[a].fitness<Pop1[b].fitness) 
  328.             swap(&a,&b) ;
  329.         ga_simplex(Pop1[a].gene,Pop1[b].gene,Pop2[c].gene);
  330.     }
  331.     temp=Pop1 ;
  332.     Pop1=Pop2 ;
  333.     Pop2=temp ;
  334.     return 0 ;
  335. }
  336.                 
  337.